The present invention relates to a combination problem solving method which determines such a combination of occurrences of events as meeting a given condition and an image segmentation method which segments a specific object from an image and is required for design segmentation and so on.
Conventionally, a highly interconnected neural network has been available for solving a combination problem. Whether or not the events occur in the combination problem corresponds to whether or not the corresponding neurons fire. In other words, the occurrences of the events in the combination problem match to the firing of the corresponding neurons in the network. The better a given condition is satisfied, the smaller the value of an energy function is set. The states of the neurons are transitioned properly so that the energy value may become as small as possible. That is, by the overall network to the minimum energy state, it is possible to solve a proper combination problem. The application of the highly interconnected neural network to a Traveling-Salesman Problem results in being able to obtain a considerably proper approximate solution as discussed in AIHARA Kazuyuki: Current State of Study on Neural Computer, Learning from Brain and Neuron, Denki University Edition (1988), pages 98 to 105 (First Prior Art) and Aso Hideki: Neural Network Information Processing, Sangyo-Tosho (1988), pages 118 to 123 (Second Prior Art). In these prior arts the Traveling-Salesman Problem in N cities is considered as a combination problem wherein N.times.N units arranged in a square are prepared for considering each row as one city and if the j-th column unit is 1, the visiting turn of the city is j-th.
The characteristics of an energy function of a Hopfield type neural network, that is, one of the highly interconnected neural networks and the method for properly setting an energy function in a highly interconnected neural network have been discussed in Abe Shigeo: Theoretical View on Hopfield type Neural Network, 38th National Meeting of Information Processing Society (in the first-half time of 1989), pages 470-471, (Third Prior Art) and Abe Shigeo: Characteristics of Convergence of Hopfield type Neural Network, National Meeting of Electric Society, 1988, pages 12-1, 12-2, (Fourth Prior Art).
In the magazine: "bit", vol. 22, No. 8, Kyouritu ed., (1990), pages 920 to 921 (Fifth Prior Art), the disclosure states that in designing an energy function each term should be normalized for preparing for later expansion. Further, to keep a balance between the terms as much as possible even if the values of the size and cost of the problem are changed, it is proposed that the cost value is divided by its average value.
Today, research and development have been active on the system handling images which have an affluent representative capability such as a presentation system used in a show window. To make more effective use of image representation, image simulation methods such as compositing into a background image or change of an object color have been widely used in design simulation of domestic electric equipment.
To carry out such an image simulation, it is necessary to cut out a specific object from an image. The cut-out technique is called an image segmentation technique. For example, the image segmentation technique means that only a car image is separated from the overall image representing the car running in a street inside a city. The image simulation technique means that, for example, the separated car image is buried in the landscape on the outskirts of the city.
A method about the image segmentation has been proposed where the coordinates representing the contour of an object are directly input by an external input device like a mouse without using the image processing technique for cutting out the image. In this method a cursor is displayed on the screen synchronous to the movement of the mouse and a user operates the mouse to move the cursor along the contour of an object to be cut. The trace of the moving mouse matches to the contour of the object.
As to the other research associated with the image segmentation there is a system called SNAKE using a dynamic model. This system is discussed in Proceedings of First International Conference on Computer Vision (1987), IEEE Computer Society press, pp. 259 to 268 (Sixth Prior Art). The system uses a method for obtaining such a curve as minimizing an energy functional made of an external constraint force, an image force, and an internal force for obtaining a contour of an object in an image.
As to the combination problem, it is necessary to newly set an energy function each time the object problem changes, because the energy function depends on the object problem. That is, if the difference between a new combination problem and the current combination problem is just a size, the energy function also changes no matter how analogous both of the combination problems are.
In the prior art, the proper energy function for solving a combination problem is not allowed to be used for another combination problem. As such, it is necessary to set an energy function for each combination problem. The fifth prior art discusses that the energy function should be normalized, while no concrete method for normalization is discussed.
As to the image segmentation method, how to solve the problem of cutting a specific object from an image will be described with the problem being a problem for obtaining pixels corresponding to the contour of the specific object by using the state transition of the highly interconnected type neural network. Further, the prior art discussing the image segmentation method will be described as well.
The solution of the cutting problem will be realized by the following routine, for example.
At first, an image is input and displayed on screen. Next, a user points to a rough contour of an object to be cut. A band-like area (meaning an area having a given width) is created around the rough contour pointed to by the user. Then, the band-like area is normalized to be a slender rectangle and the pixel values are re-sampled from an original image for creating a band-like image. By detecting edges from the band-like image with the image processing method, the edge map is created for the band-like image. Consider a highly interconnected type neural network where the pixels of the band-like image correspond to the neurons. The state of the neural network is transitioned so that the neurons located on the contour of the band-like image serve to fire. Last, by obtaining the contour from the most appropriate state of the neural network obtained by the transition, a mask image of the object is created and then is output.
In order to transition the state of the neural network so that the neurons located on the contour serve to fire, the energy function can be set to have a small value as the fired neurons meet the below-indicated conditions. First, only one neuron exists perpendicularly to the contour (in the vertical direction of the contour). Second, those neurons are chained smoothly along the contour (in the horizontal direction of the contour). Third, those neurons reflect the pixels detected as image edges by the image processing. Fourth, the contour depicted by those neurons is near to the contour input from the outside.
The energy function E associated with the conditions is represented as follows ##EQU1## wherein x and y denote vertical coordinates of the band-like image, i is a horizontal coordinate of the band-like image, V.sub.xi is a neuron representing a pixel at the location (x,i), V.sub.xi has any value ranging from 0 to 1, if the pixel is considered perfectly as a part of contour, the neuron has a value of 1, and if not at all, a value of 0.V.sup.0 xi denotes an edge map having any value ranging from 0 to 1, if it matches to an edge, it has a value of 1 and if not, a value of 0, j denotes a vertically scanning index having a value ranging from -a to a, dj represents a distance between neurons when the distance between th pixels on one column and the adjacent column is j.1xi represents the distance between the location (x,i) and the rough contour pointed from the outside, A, B, C, D, E, F are real coefficients.
The terms of the coefficients A and B offer a more advantageous energy function if only one contour pixel exists in the column (vertical) direction. Those two terms become minimum, if only one pixel located in the column direction merely has a value of 1. The term of the coefficient C offers a more advantageous energy function if the pixels depicting the contour are smoothly chained in the horizontal direction. For those pixels, the scanning is done on both of the adjacent neural columns by (2a+1) pixels. The term becomes a more advantageous energy function as the vertical distance between the adjacent neurons both having a non-zero value in each neural column becomes smaller, because the energy becomes smaller as that vertical distance becomes smaller. Hence, along the horizontal direction, the pixels having a value of 1 often have the similar vertical coordinates. The term of the coefficient D offers a more advantageous energy function as the pixels considered to be part of the contour are more reflective on the edge map. That is, if a neuron has a value of 1, the term offers a more advantageous energy function for the neuron located on the edge map than the neuron located out of the edge map. The term of the coefficient E is a term for setting how easily the neuron fires. The term of the coefficient F offers a more advantageous energy function as the pixels representing the contour is closer to the rough contour pointed from the outside. This term offers a more advantageous energy function if two or more pixels in one neural column are detected as edges of the edge map and the neuron fires at the closest pixel to the rough contour.
The actual procedure will be described below ##EQU2## wherein u denotes an internal state of a neuron, t denotes a time, .tau. and u.sub.0 denote constants.
In accordance with a dynamic model represented by the formula (2), the network is transited in the direction of reducing the energy, resulting in obtaining a desirous contour.
The energy function, however, depends on the subject problem. Hence, each time the subject combination problem has another size, the coefficients of the energy function are required to be changed.